package leetcode.linkedlist;


/**
 * 2. 两数相加
 *
 */
public class AddTwoNumbers {

    public static void main(String[] args) {
        AddTwoNumbers solution = new AddTwoNumbers();
        Integer[] arr1 = {9, 9, 9, 9, 9, 9, 9};
        Integer[] arr2 = {9, 9, 9, 9};
        ListNode l1 = ListNode.makeLinkedList(arr1);
        ListNode l2 = ListNode.makeLinkedList(arr2);

        ListNode resList = solution.addTwoNumbers(l1,l2);
        System.out.println(resList);
    }

    /**
     * 两数相加
     *
     * @param l1    单链表
     * @param l2    单链表
     * @return
     */
    public ListNode addTwoNumbers0(ListNode l1, ListNode l2) {
        // 进位值
        int carry = 0;
        // 新链表的头节点
        ListNode head = new ListNode();
        ListNode tail = null;

        while (l1 != null || l2 != null) {
            int value1 = l1 == null ? 0 : l1.val;
            int value2 = l2 == null ? 0 : l2.val;
            int sum = value1 + value2 + carry;
            // 余数
            int value = sum % 10;
            // 商
            carry = sum / 10;

            // 添加节点
            if(tail == null) {
                // 头节点设值
                tail = head;
                // 头节点
                tail.val = value;
            }else {
                tail.next = new ListNode(value);
                tail = tail.next;
            }


            // 指针后移
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }

        if(carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }

    /**
     * 两数相加 官方写法
     *
     * @param l1    单链表
     * @param l2    单链表
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 新链表需要使用两个指针, 一个指向头节点, 一个用于遍历添加新节点
        ListNode head = null, tail = null;
        // 进位值
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                // 添加头节点
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }

}
